package org.example.myleet.p419;

public class Solution {

    private static int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private int count;

    private int m;
    private int n;

    public int countBattleships(char[][] board) {
        count = 0;
        m = board.length;
        n = board[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'Y') {
                    board[i][j] = 'X';
                }
            }
        }
        return count;
    }

    private void dfs(char[][] board, int r, int c) {
        int nextR = -1;
        int nextC = -1;
        for (int[] direction : DIRECTIONS) {
            int nr = r + direction[0];
            int nc = c + direction[1];
            if (0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] == 'X') {
                nextR = nr;
                nextC = nc;
                break;
            }
        }
        board[r][c] = 'Y';
        if (nextR >= 0) {
            dfs(board, nextR, nextC);
        } else {
            ++count;
        }
    }
}
